#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# find absence number from a list

import time
import random

# method 1
def find_absence(lst):
    lst = sorted(lst)
    lst_end = lst[-1]
    normal_sum = 0
    for i in range(1, lst_end + 1):
        normal_sum += i
    absence_sum = 0
    for i in lst:
        absence_sum += i
    return normal_sum - absence_sum


# method 2
def find_absence_2(lst):
    lst = sorted(lst)
    _len = len(lst) - 1
    for i in range(_len):
        if lst[i + 1] - lst[i] != 1:
            return lst[i] + 1


if __name__ == '__main__':

    upper = 10000000
    target = random.randint(1, upper - 1)

    lst = [n for n in range(1, upper) if n != target]
    
    start = time.time()
    print(find_absence(lst) == target)
    end = time.time()
    print('run method 1 spend time is %.3f' % (end - start))

    start = time.time()
    print(find_absence_2(lst) == target)
    end = time.time()
    print('run method 2 spend time is %.3f' % (end - start))




